// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem174.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=174 lang=cpp
 *
 * [174] 地下城游戏
 */

// @lc code=start
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<int> dp(n);
        
        dp[n - 1] = 1 - dungeon[m - 1][n - 1];
        dp[n - 1] = dp[n - 1] <= 0 ? 1 : dp[n - 1]; 

        for (int j = n - 2; j >= 0; --j) {
             dp[j] = (dp[j + 1] - dungeon[m - 1][j]) <= 0 ? 1 : (dp[j + 1] - dungeon[m - 1][j]);
            }
        
        

        for (int i = m - 2; i >= 0; --i) {
            dp[n - 1] = (dp[n - 1] - dungeon[i][n - 1]) <= 0 ? 1 : (dp[n - 1] - dungeon[i][n - 1]);
            for (int j = n - 2; j >= 0; --j) {
                dp[j] = min(dp[j], dp[j + 1]) - dungeon[i][j];
                dp[j] = dp[j] <= 0 ? 1 : dp[j];
            }
        }

        return dp.front();
    }
};
// @lc code=end

